/*
给定一个数，将链表划分为<,=,>区域，返回划分完成后的链表头指针
额外空间复杂度为O(1), 节点之间的相对次序要保证(保证稳定性)

思路:
lessHead, lessEnd
equalHead, equalEnd
moreHead, moreEnd
链表节点拼接
 */
import LinkedList from '../../datastructure/linkedlist/linkedlist'

/**
 *
 * @param {Node} head
 * @param {number} target
 * @return {Node}
 */
function partitionLinkedlist (head, target) {
  if (!head) {
    return null
  }
  let lessHead = null
  let lessEnd = lessHead
  let equalHead = null
  let equalEnd = equalHead
  let moreHead = null
  let moreEnd = moreHead
  while (head !== null) {
    if (head.element < target) {
      if (!lessHead) {
        lessHead = head
        lessEnd = head
      } else {
        lessEnd.next = head
        lessEnd = lessEnd.next
      }
    } else if (head.element === target) {
      if (!equalHead) {
        equalHead = head
        equalEnd = head
      } else {
        equalEnd.next = head
        equalEnd = equalEnd.next
      }
    } else {
      if (!moreHead) {
        moreHead = head
        moreEnd = head
      } else {
        moreEnd.next = head
        moreEnd = moreEnd.next
      }
    }
    head = head.next
  }
  // 开始拼接
  if (lessEnd !== null) {
    lessEnd.next = equalHead !== null ? equalHead : moreHead
  }
  if (equalEnd !== null) {
    equalEnd.next = moreHead
  }

  return lessHead !== null ? lessHead : equalHead !== null ? equalHead : moreHead
}

const linkedList = new LinkedList()
for (const i of [3, 7, 8, 2, 1, 5, 6, 4, 5, 9]) { linkedList.push(i) }
const head = partitionLinkedlist(linkedList.head, 5)
let str = ''
for (let p = head; p !== null; p = p.next) {
  str += p.element + '->'
}
str = str + 'null'
console.log(str)
